package com.leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 数组全排列
 */
public class Leet46 {
	public static void main(String[] args) {
		new Leet46().permute(new int[]{1, 2, 3});
	}
	public List<List<Integer>> permute(int[] nums) {
		List<List<Integer>> res=new ArrayList();
		if(nums.length==0)return res;

//		backTrace(0,nums,res,null);
		backTrace2(0,nums,res);
		return res;
	}

	/**
	 * 传小list是真的不熟练,还出错!!,退出投机倒把不优雅!!
	 */
	public void backTrace(int idx,int[] nums,List<List<Integer>> res,List<Integer> l){
		if(idx==nums.length-1){
			l.add(nums[nums.length-1]);
			res.add(l);
			return;
		}

		for(int a=idx;idx<nums.length;a++){
			swap(nums,idx,a);
			if(idx==0){
				l=new ArrayList();
			}
			l.add(nums[idx]);
			backTrace(idx+1,nums,res,l);
			swap(nums,idx,a);
		}
	}

	/**
	 * 考点:退出条件,如何优雅
	 */
	public void backTrace2(int idx,int[] nums,List<List<Integer>> res){
		if(idx==nums.length-1){
			List<Integer> l=new ArrayList();
			for (int i = 0; i < nums.length; i++) {
				l.add(nums[i]);
			}
			res.add(l);
			return;
		}

		for (int a = idx; a < nums.length; a++) {
			swap(nums,idx,a);
			backTrace2(idx+1,nums,res);
			swap(nums,idx,a);
		}
	}
	public void swap(int[] nums,int a,int b){
		int temp=nums[a];
		nums[a]=nums[b];
		nums[b]=temp;
	}
}
